Due to the increasing need for rapid matching capabilities, content addressable memories (CAMs) continue to proliferate. A CAM may perform matching functions by applying a search key or “comparand” to a table of stored data values. A CAM may then determine if any of the data values match a given search key.
CAM devices may take a variety of forms. As but a few of the possible examples, some CAM devices are based on particular types of CAM cells. Such cells may include storage circuits integrated with compare circuits. Examples of storage circuits may be static random access memory (SRAM) type cells or dynamic RAM (DRAM) type cells. Alternate approaches may include RAM arrays, or the like, with separate matching circuits and/or processes.
Referring now to FIG. 9, a conventional CAM device is set forth in a block diagram and designated by the general reference character 900. A conventional CAM device 900 may include a number of entries (ENTRY0 to ENTRYn) 902 and a priority encoder 904. Each entry (ENTRY0 to ENTRYn) may store a data value for comparison with an applied key value KEY. In a conventional compare operation, a key value KEY can be applied to entries (ENTRY0 to ENTRYn) essentially simultaneously. That is, a key value KEY can be applied to all entries (ENTRY0 to ENTRYn).
Each entry (ENTRY0 to ENTRYn) can generate a corresponding match indication (MATCH0 to MATCHn) that can reflect whether or not data for an entry matches an applied key value. More a particularly, if entry data matches a key value, a corresponding match indication can be active. If entry data does not match a key value, a corresponding match indication can be inactive.
Priority from among multiple active match indications can be established by a priority encoder 904. More particularly, a conventional priority encoder 904 can prioritize match indications according to a “physical” priority of the entries. A physical priority can be a priority established by a physical location of an entry on a conventional CAM device. Typically, physical priority can correspond to an address of an entry, with a lower address value having priority over a higher address value.
In the example of FIG. 9, a priority encoder 904 can encode a highest priority match indication into an index value INDEX. In some conventional approaches, an index value can be used to access associated data, or alternatively, a highest priority match indication can access associated data directly.
In a conventional approach, some entries may be considered “invalid” and thus may be excluded from generating a match indication. Conventionally, invalid entries can be distinguished from valid entries by a valid bit. That is, valid entries may have a valid bit set to one value (e.g., 1), while invalid entries may have a valid bit set to another value (e.g., 0). In a conventional compare operation, a valid bit value of “1” may be applied in combination with a key, thus forcing invalid entries to “not match” a key value.
Use of valid bits can result in the capability of “per entry” granularity. That is, a key value may be applied to each entry, with entries being excluded or included according to all or a portion of a data value stored within an entry.
Examples of conventional CAM systems will now be described.
A first conventional CAM system is shown in FIG. 10 and designated by the general reference character 1000. A conventional CAM system 1000 may include one or more CAM devices, each of which may perform CAM related operations, such as searches, or the like. In the example of FIG. 10, a CAM system 1000 includes “n+1” CAM devices, shown as 1002-0 to 1002-n. A CAM system 1000 may perform operations in response to commands from a requesting device. In FIG. 10, a requesting device is a network processing unit (NPU) 1004.
FIG. 10 shows an example of a bus based CAM system. In a bus based CAM system, CAM devices may be commonly connected to a requesting device and to one another by a common bus. Thus, in FIG. 10 CAM devices (1002-0 to 1002-n) can be commonly connected to each other and to an NPU 1004 by a bus 1006.
A second conventional CAM system is set forth in FIG. 11 and designated by the general reference character 1100. A second conventional CAM system 1100 may include a number of CAM devices (1102-0 to 1102-3) having common connections to a command and data bus 1104, as well as separate common connections to an index or result bus 1106. Optionally, an index or result bus 1106 may be connected to one or more memory devices 1108, such as a static random access memory (SRAM).
In a system like that shown in FIG. 11, a search command may be issued from a host device 1110 on a command and data bus 1104. CAM devices (1102-0 to 1102-3) may process such a command and generate results, which may be output on an index or result bus 1106. Results may be returned to a command issuing host device 1110 by way of a result bus. Optionally, results may be applied to one or more memory devices 1108 to generate associated data that may then be accessed by a host device 1110.
A drawback to conventional systems, like those set forth in FIGS. 10 and 11, can be limited flexibility in how operations may be executed within such systems and/or how data may be arranged within CAM entries of a system. For example, in the case of a search operation, a key value may be applied to all entries of a CAM device. It can be possible to exclude search operations from one or more CAM devices by way of a “chip enable” control signal, or the like. However, the “granularity” of such a search remains on a device-by-device basis with respect to the system, and an entry-by-entry basis with respect to individual devices.
Similarly, search results generated from a search or other operations may have a same granularity. In particular, in FIG. 10, each CAM device (1002-0 to 1002-n) may provide a range of index values or associated data values, where such index and/or associated data values is associated with a single entry. In FIG. 1, a CAM device (1102-0 to 1102-n) can apply output results (e.g., index values) to a given associated data device (e.g., an SRAM 1108).
It would be desirable to provide more variation in the way in which operations, such as search operations, can be executed within a CAM device. In particular, it would be desirable to provide variations in granularity of search and/or other CAM operations.